import math
import gmpy
def gen_palindroms(k, lz = False):
    '''
    Generate palindroms as string with fixed length k
    '''
    if k == 0:
        return ['']
    if k == 1:
        return list('123456789' if not lz else '0123456789')
    return sum(map(lambda palindrom: map(lambda x: x + palindrom + x, '123456789' if not lz else '0123456789'), gen_palindroms(k-2, True)), list())

def rep_unit_len(n):
    '''
    Rep unit is a number consisting entirely of ones.
    Return the len of the smallest rep unit such that rep unit % n == 0
    '''
    rl = 0
    r = 0
    while r != 1:
        rd = r%10
        for d in range(0,10):
            if (d * n + rd) % 10 == 1:
                rl += 1
                r = (d * n + rd) / 10 + r / 10
    return rl + 1

def partial_divide(n, last_digits):
    '''
    Return the smallest number such as when multiple n by it the last digits are last_digits
    '''
    rl = 0
    r = 0
    while len(last_digits) > 0:
        rd = r%10
        for d in range(0,10):
            if (d * n + rd) % 10 == last_digits[-1]:
                last_digits.pop()
                rl += 1
                r = (d * n + rd) / 10 + r / 10
                yield d
                break


def is_integer(n):
    return n % 1 == 0

def is_square(n):
    return gmpy.is_square(n)

def gen_relatively_primes(n, a=1, b=1):
    ### generates all relatively prime pairs <= n.  The larger number comes first.
    yield (a,b)
    k = 1
    while a*k+b <= n:
        for i in gen_relatively_primes(n, a*k+b, a):
            yield i
        k += 1

def factors(n):
    for p in range(1,int(math.sqrt(n)) + 1):
        if n % p == 0:
            yield (n/p,p)
def fib():
    "unbounded generator, creates Fibonacci sequence"
    x = 0
    y = 1
    while True:
        yield x
        x, y = y, x + y
